package leetcode.D300.T297;

import util.TreeNode;
import util.TreeUtil;

import java.util.Deque;
import java.util.LinkedList;

public class H297 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right  = new TreeNode(3, new TreeNode(4), new TreeNode(5));
        TreeUtil.printPreorder(root);
        Codec codec = new Codec();
        String s = codec.serialize(root);
        System.out.println(s);
        String[] array = s.split(",");
        TreeNode newRoot = codec.deserialize(s);
        TreeUtil.printPreorder(newRoot);
    }

    // 一刷
    /*private static class Codec {
        private final static char SEP = ',';
        private final static char NULL = '#';

        public String serialize(TreeNode root) {
            if(root == null) {
                return "";
            }
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Deque<TreeNode> dq = new LinkedList<>();
            dq.addLast(root);
            while(!dq.isEmpty()) {
                TreeNode front = dq.removeFirst();
                if(front != null) {
                    sb.append(String.valueOf(front.val)).append(SEP);
                    dq.addLast(front.left);
                    dq.addLast(front.right);
                } else {
                    sb.append(NULL).append(SEP);
                }
            }
            sb.append("]");
            return sb.toString();
        }
        public TreeNode deserialize(String data) {
            if(data == "") return null;
            String[] dataList = data.substring(1, data.length()-1).split(String.valueOf(SEP));
            TreeNode root = new TreeNode(Integer.parseInt(dataList[0]));
            Deque<TreeNode> dq = new LinkedList<>();
            dq.addLast(root);
            int pos = 1;
            while(!dq.isEmpty()) {
                TreeNode front = dq.removeFirst();
                if(!String.valueOf(NULL).equals(dataList[pos])) {
                    front.left = new TreeNode(Integer.parseInt(dataList[pos]));
                    dq.addLast(front.left);
                }
                ++pos;
                if(!String.valueOf(NULL).equals(dataList[pos])) {
                    front.right = new TreeNode(Integer.parseInt(dataList[pos]));
                    dq.addLast(front.right);
                }
                ++pos;
            }
            return root;
        }
    }*/

    // 二刷
    private static class Codec {
        private static final String SEP = ",";
        private static final String NUL = "#";

        private int idx = 0;

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.toString();
        }

        private void serialize(TreeNode root, StringBuilder sb) {
            if (root == null)
                sb.append(NUL).append(SEP);
            else {
                sb.append(root.val).append(SEP);
                serialize(root.left, sb);
                serialize(root.right, sb);
            }
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] splits = data.split(SEP);
            return deserialize(splits);
        }

        private TreeNode deserialize(String[] splits) {
            if (splits[idx].equals(NUL)) {
                idx++;
                return null;
            }
            TreeNode node = new TreeNode(Integer.parseInt(splits[idx++]));
            if (idx == splits.length)
                return node;
            node.left = deserialize(splits);
            if (idx == splits.length)
                return node;
            node.right = deserialize(splits);
            return node;
        }
    }
}




